package org.zlb.algorithm.sort;

/**
 * 快速排序（冒泡排序的改进）
 *
 * @author zhoulingbo
 * @date 2021/7/16 10:25
 */
public class QuickSort extends AbstractSort {

    @Override
    public void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    void sort(int[] arr, int start, int end) {
        if (end <= start)
            return;
        int temp = arr[start];
        int i = start;
        int j = end;
        while (i < j) {

            while (j > i) {
                if (arr[j] < temp) {
                    swap(arr, j, i);
                    break;
                }
                j--;
            }

            while (i < j) {
                if (arr[i] > temp) {
                    swap(arr, i, j);
                    break;
                }
                i++;
            }
        }

        sort(arr, start, i - 1);
        sort(arr, i + 1, end);
    }
}
